package 系统复习.面试题.区间集合;

/**
 * 给定字符串 s 和字符串数组 words。
 * 对于 s 内部的子字符串，若其存在于 words 数组中， 则通过添加闭合的粗体标签 <b> 和 </b> 进行加粗标记。
 * 如果两个这样的子字符串重叠，你应该仅使用一对闭合的粗体标签将它们包围起来。
 * 如果被粗体标签包围的两个子字符串是连续的，你应该将它们合并。
 * 返回添加加粗标签后的字符串 s 。
 */
public class L616 {

    public String addBoldTag(String s, String[] words) {
        int len = s.length();
        boolean[] marks = new boolean[len];
        for(int i = 0 ; i < words.length;i++){
            int start = 0;//每次循环都要从s的0位置开始找
            int w_len = words[i].length();
            int idx = s.indexOf(words[i]);//第一次搜索s，是否有words[i]
            while(idx != -1){
                for(int k = idx;k < idx + w_len;k++){
                    marks[k] = true;//加粗就标记true。
                }
                idx = s.indexOf(words[i], idx + 1);
                //类似于"ssss"，加粗字符是"sss"的话，四个s其实都要加粗。所以这里要在找到的位置+1继续找
            }
        }
        StringBuilder res = new StringBuilder();
        char[] chars = s.toCharArray();//因为要遍历整个字符串，所以从String变成charArray更快
        int left = 0,right = 1;
        boolean boldTag = false;
        if(marks[0]) {
            res.append("<b>");
            boldTag = true;
        }
        while(right < len){
            if(marks[right] != marks[left]){
                res.append(chars,left,right - left);//注意append(char[],start,len)和String的subString不一样
                if(boldTag){
                    res.append("</b>");
                    boldTag = false;
                }else{
                    res.append("<b>");
                    boldTag = true;
                }
                left = right;
            }
            right++;
        }
        res.append(chars,left,right - left);//处理结尾部分
        if(boldTag){
            res.append("</b>");
        }
        return res.toString();
    }

    public static void main(String[] args) {
        L616 l616 = new L616();
        System.out.println(l616.addBoldTag("abcxyz123", new String[]{"abc", "123"}));
    }
}
